package com.example.slidingwindow;

import java.util.Arrays;

/**
 * 给定一个含有 n 个正整数的数组和一个正整数 target 。
 *  找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。
 *  如果不存在符合条件的子数组，返回 0 。
 *
 *  示例 1：
 * 输入：target = 7, nums = [2,3,1,2,4,3]
 * 输出：2
 * 解释：子数组[4,3]是该条件下的长度最小的子数组。
 *
 *  示例 2：
 * 输入：target = 4, nums = [1,4,4]
 * 输出：1
 *
 *  示例 3：
 * 输入：target = 11, nums = [1,1,1,1,1,1,1,1]
 * 输出：0
 */
public class Leetcode209_MinSubArrayLen {
    public static void main(String[] args) {
        int target = 7;
        int[] nums;
        nums = new int[] {2, 3, 1, 2, 4, 3};
//        nums = new int[] {1, 1, 1, 1, 1, 1, 1, 1};
        System.out.println(new Solution().minSubArrayLen(target, nums));

    }

    static class Solution {
        /**
         * 解法三:滑动窗口(可收缩的)
         * 思路:
         * 滑动窗口两端left,right
         * 当窗口里的元素和大于或等于target 计算窗口长度并更新结果,然后将窗口左侧的元素移出窗口,最后left++
         * 当窗口里的元素和小于target right++;
         * @param target
         * @param nums
         * @return
         */
        private int minSubArrayLen3(int target, int[] nums) {
            int res = Integer.MAX_VALUE;
            int left = 0, right = 0;
            int sum = 0;

            while (right < nums.length) {
                sum += nums[right];

                while (sum >= target) {
                    res = Math.min(res, right - left + 1);
                    sum -= nums[left++];
                }

                right++;
            }

            return res == Integer.MAX_VALUE ? 0 : res;
        }

        /**
         * 解法二:前缀和 + 二分查找
         * 因为这道题保证了数组中每个元素都为正,所以前缀和一定是递增的,这一点保证了二分的正确性。
         * 如果题目没有说明数组中每个元素都为正，就不能使用二分来查找这个位置了
         * 思路:
         * 利用前缀和的sum[i] - sum[j] = s 表示(i,j)之间的和为s进行查找
         * 实现:
         * 对于每个开始下标 i,通过二分查找得到大于或等于 i 的最小下标 bound,使得 preSums[bound]−preSums[i−1]>=target
         * 并更新子数组的最小长度（此时子数组的长度是bound−(i−1)）
         *
         * @param target
         * @param nums
         * @return
         */
        private int minSubArrayLen2(int target, int[] nums) {
            if (nums.length == 0 || nums == null)
                return 0;
            int res = Integer.MAX_VALUE;
            int[] preSums = new int[nums.length + 1]; // preSums[i]表示0到i-1的前缀和
            // 初始化前缀和
            for (int i = 1; i < preSums.length; i++) {
                preSums[i] = preSums[i - 1] + nums[i - 1];
            }
            // 2, 3, 1, 2, 4, 3
            // 0, 2, 5, 6, 8, 12, 15
            for (int i = 1; i <= nums.length; i++) {
                int tmp = preSums[i - 1] + target; // 查找得到大于或等于 i 的最小下标 bound,使得 preSums[bound]−preSums[i−1]≥target
                int bound = Arrays.binarySearch(preSums, tmp); //
//                System.out.print("i: " + i + " tmp: " + tmp + " b: " + bound);
                if (bound < 0) { // 没有找到tmp,就将索引置为比tmp小的最大值的位置
                    bound = -bound - 1;
                }

                if (bound <= nums.length) {
                    res = Math.min(res, bound - (i - 1));
                }
//                System.out.println(" index: " + bound +" res: " + res);
            }
            return res == Integer.MAX_VALUE ? 0 : res;
        }

        /**
         * 暴力法:
         * 遍历所有可能的子数组求和，然后比较
         * @param target
         * @param nums
         * @return
         */
        private int minSubArrayLen1(int target, int[] nums) {
            if (nums.length == 0 || nums == null)
                return 0;
            int res = Integer.MAX_VALUE;
            for (int i = 0; i < nums.length; i++) {
                int sum = 0;
                for (int j = i; j < nums.length; j++) {
                    sum += nums[j];
                    if (sum >= target) {
                        res = Math.min(res, j - i + 1);
                        break;
                    }
                }
            }
            return res == Integer.MAX_VALUE ? 0 : res;
        }

        public int minSubArrayLen(int target, int[] nums) {
            return minSubArrayLen3(target, nums);
        }
    }
}
